﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using FindGreatestLinkedNode.Question;
namespace FindGreatestLinkedNode.Answer
{
    class Effie : IFindNearestGreatestNodeInBinaryTree
    {
        public Node FindNodeByDataValue(Node node, int DataValue, out Node curNode)
        {
            curNode = null;
            if (node.Data == DataValue)
            {
                curNode = node;
                return curNode;
            }

            if (node.LeftChild != null)
            {
                if (node.LeftChild.Data == DataValue)
                {
                    curNode = node.LeftChild;
                    return node;
                }
                else
                {
                    Node node_temp = FindNodeByDataValue(node.LeftChild, DataValue, out curNode);
                    if (node_temp != null)
                        return node_temp;
                }
            }

            if (node.RightChild != null)
            {
                if (node.RightChild.Data == DataValue)
                {
                    curNode = node.RightChild;
                    return node;
                }
                else
                {
                    Node node_temp = FindNodeByDataValue(node.RightChild, DataValue, out curNode);
                    if (node_temp != null)
                        return node_temp;
                }
            }
            return null;
        }

        #region IFindNearestGreatestNodeInBinaryTree Members

        public int? FindNearestGreatestNode(Node root, int k)
        {
            int MaxDataValue = -1;
            if (root == null)
                return MaxDataValue;

            Node curNode = null;
            Node p_Node = this.FindNodeByDataValue(root, k, out curNode);

            if (curNode == null || p_Node == null)
                return -1;

            if (p_Node.Data == curNode.Data)
            {
                int left = curNode.LeftChild == null ? -1 : curNode.LeftChild.Data;
                int right = curNode.RightChild == null ? -1 : curNode.RightChild.Data;

                if (left > right)
                {
                    if (left > curNode.Data)
                        return left;
                    else
                        return null;
                }
                else
                {
                    if (right > curNode.Data)
                        return right;
                    else
                        return null;
                }
            }
            else
            {
                int nodedate = p_Node.Data;
                int left = curNode.LeftChild == null ? -1 : curNode.LeftChild.Data;
                int right = curNode.RightChild == null ? -1 : curNode.RightChild.Data;

                if (nodedate > left)
                {
                    if (nodedate > right)
                    {
                        if (nodedate>curNode.Data)
                            return nodedate;
                        else
                            return null;
                    }
                    else if (right >curNode.Data)
                    {
                        return right;
                    }
                    else
                        return null;
                }
                else
                {
                    if (left > right)
                    {
                        if (left > curNode.Data)
                            return left;
                        else
                            return null;
                    }
                    else
                    {
                        if (right > curNode.Data)
                            return right;
                        else
                            return null;
                    }
                }
            }
        }
        #endregion
    }
}
